package 困难.滑动窗口;

/**
 * 给你一个整数数组 nums 和一个整数 k 。 nums 仅包含 0 和 1 。
 * 每一次移动，你可以选择 相邻 两个数字并将它们交换。
 * 请你返回使 nums 中包含 k 个 连续 1 的 最少 交换次数。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/minimum-adjacent-swaps-for-k-consecutive-ones
 */
public class 得到连续K个1的最少相邻交换次数_1703 {

    public static void main(String[] args) {

        System.out.println(minMoves(new int[]{1, 0, 0, 0, 0, 0, 1, 1}, 3));

    }

    /**
     * 贪心思路，容易想到，尽可能将相邻的 1 聚在一起，可以使得
     * 和 0 交换的次数少，可以用滑动窗口，每个窗口里面最多有
     * k 个 1 ，取其中窗口最少交换次数即可
     * 如何求某个窗口中将 k 个 1 聚在一起的最少交换次数，
     * 逆向思维，其实是将里面的 0 往边缘推去，例如：
     * 10110 ，对应第一个 0 将其移动至最右边还是最左边，取决
     * 于其左边和右边 1 的个数，优先向左交换 1 次
     * 可使用前缀和取得某个 0 左右两边 1 的个数
     */
    public static int minMoves(int[] nums, int k) {
        int minCost = Integer.MAX_VALUE;
        int left = 0, right = 0;
        int curK = 0;
        while (left < nums.length) {
            while (right < nums.length && curK < k) {
                if (nums[right] == 1) {
                    curK++;
                }
                right++;
            }

            if (curK == k) {
                int curCost = 0;
                int[] prefixSum = new int[right - left];
                prefixSum[0] = nums[left];
                for (int i = 1; i < prefixSum.length; i++) {
                    prefixSum[i] = prefixSum[i - 1] + nums[left + i];
                }

                for (int i = 0; i < prefixSum.length; i++) {
                    if (nums[left + i] == 0) {
                        curCost += Math.min(prefixSum[i], prefixSum[prefixSum.length - 1] - prefixSum[i]);
                    }
                }

                minCost = Math.min(minCost, curCost);
            }

            while (left < nums.length && nums[left] == 0) {
                left++;
            }
            left++;
            curK--;
        }

        return minCost;
    }

}
